Fiolki [B]
Limit pamięci: 128 MB
Bajtazar jest chemikiem.
Przeprowadza eksperyment, którego celem jest uzyskanie specyfiku X -
mikstury rozwiązującej wszelkie problemy ludzkości.
Bajtazar posiada fiolek ponumerowanych liczbami od do ,
w których znajdują się różne płynne substancje.
Fiolka o numerze zawiera całkowitą liczbę gramów substancji .
Aby uzyskać specyfik X, należy wykonać sekwencję kroków.
Każdy krok polega na przelaniu całej zawartości pewnej fiolki do innej
(możemy przy tym założyć, że fiolki mają odpowiednio dużą pojemność,
a także, że przy przelewaniu nie uronimy ani kropli).
Fiolka, z której przelano substancję, jest odstawiana na półkę i nie jest wykorzystywana
w dalszej części eksperymentu.
O pewnych parach substancji wiadomo, że reagują ze sobą, tworząc
związek chemiczny, który wytrąca się w postaci osadu.
Dla każdej takiej reakcji, na jeden gram pierwszej substancji
przypada jeden gram drugiej, a w jej wyniku powstają
dwa gramy osadu.
Reakcja trwa, dopóki któryś z jej substratów się nie skończy.
Wytrącony osad nie reaguje z żadną substancją i
do końca eksperymentu przylega do ścianki fiolki,
w której powstał.
Pewne reakcje dokonują się szybciej niż inne - jeśli wiele
substancji znajdzie się naraz w jednym
roztworze, reakcje pomiędzy parami substancji wykonują się
w ustalonej, znanej Bajtazarowi kolejności.
Po każdym kroku Bajtazar czeka, aż substancje w docelowej fiolce przereagują,
i dopiero wtedy wykonuje kolejny krok.
Bajtazar zastanawia się, czy sekwencja kroków prowadząca do uzyskania specyfiku
X jest optymalna.
Chciałby wiedzieć, jaka część substratów marnuje się w wyniku
wykonania wszystkich kroków.
Poprosił Cię zatem o pomoc w znalezieniu łącznej liczby gramów
wytrąconego osadu.
Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite , oraz
(, ), oznaczające
kolejno: liczbę fiolek (a więc także liczbę różnych substancji),
długość sekwencji kroków eksperymentu
oraz liczbę par substancji, której ze sobą reagują, wytrącając osad.
W drugim wierszu znajduje się ciąg liczb całkowitych (),
określających początkową liczbę gramów substancji w fiolce numer .
W kolejnych wierszach znajduje się opis sekwencji kroków
prowadzących do uzyskania specyfiku X:
-ty z tych wierszy zawiera dwie liczby całkowite
(), oznaczające,
że -ty krok polega na przelaniu zawartości fiolki numer
do fiolki numer .
Można założyć, że jeśli w pewnym kroku wylewamy zawartość
fiolki, to ta fiolka nie zostanie użyta w żadnym z kolejnych
kroków.
W następnych wierszach znajduje się opis par substancji, które reagują
ze sobą, tworząc osad:
-ty z tych wierszy zawiera dwie liczby całkowite ,
() oznaczające,
że jeśli substancje i znajdą się jednocześnie w jednej fiolce,
to zajdzie między nimi reakcja i wytrąci się osad.
Pary substancji podane są w kolejności zgodnej z priorytetem wykonywania reakcji,
tzn. w przypadku, gdy w fiolce znajdą się się co najmniej dwie pary
reagujących ze sobą substancji,
w pierwszej kolejności rozpocznie się (i całkowicie zakończy)
reakcja pary substancji podanej na wejściu najwcześniej.
Żadna nieuporządkowana para liczb nie powtórzy
się wśród tych wierszy.
Wyjście
W jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca łączną liczbę
gramów wytrąconego osadu po wykonaniu całej sekwencji kroków eksperymentu.
Przykład
Dla danych wejściowych:
3 2 1
2 3 4
1 2
3 2
2 3
poprawną odpowiedzią jest:
6
Autor zadania: Jakub Radoszewski.